#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Heap:
    def min_lessor(a, b):
        return a < b

    def max_lessor(a, b):
        return a > b

    def build_min(self, nums, lessor=min_lessor):
        # return self.build(nums, Heap.min_lessor)
        return self.build(nums, lessor)

    def build_max(self, nums, lessor=max_lessor):
        return self.build(nums, lessor)

    def build(self, nums, lessor):
        # 通用build: 顶部放置最小元素
        start = (len(nums) - 2) // 2
        end = 0

        # print(start, end)
        for idx in range(start, end-1, -1):
            self.adjust(nums, idx, lessor)

        return nums

    # def insert_max(self, nums, value):
    #     lessor = Heap.max_lessor
    #     if lessor(value, nums[0]):
    #         nums[0] = value
    #         self.adjust(nums, 0, lessor)

    def adjust_min(self, nums, idx):
        self.adjust(nums, idx, Heap.min_lessor)

    def adjust_max(self, nums, idx, lessor):
        pass

    def adjust(self, nums, idx, lessor):
        # print("adjust", idx)
        if idx > (len(nums) - 2) // 2:
            return

        cur = nums[idx]
        left_idx  = idx * 2 + 1
        right_idx = idx * 2 + 2

        assert left_idx < len(nums)

        bottom_min_idx = 0
        if right_idx >= len(nums):
            # print("right_idx greator", idx, len(nums))
            bottom_min_idx = left_idx
        else:
            if lessor(nums[left_idx], nums[right_idx]):
                bottom_min_idx = left_idx
            else:
                bottom_min_idx = right_idx

        if lessor(nums[bottom_min_idx], nums[idx]):
            nums[idx], nums[bottom_min_idx] = nums[bottom_min_idx], nums[idx]
            self.adjust(nums, bottom_min_idx, lessor)



class Node:
    def __init__(self, value, idx_in_k):
        self.value = value
        self.idx = idx_in_k

    def __lt__(self, other):
        return self.value < other.value


def pop_heap(nums, call_back):
    if len(nums) == 0:
        return None

    top = nums[0]
    will_continue = call_back(top, nums)

    return top, will_continue


def k_way_min_intersection(k_way_inputs):
    if len(k_way_inputs) == 0:
        return -1

    k = len(k_way_inputs)
    heap_nums = []
    ks_idxs = [0] * k

    for idx, input in enumerate(k_way_inputs):
        if len(input) != 0:
            heap_nums.append(Node(input[0], idx))
        else:
            # 有空, 那么k路没有交集
            return -1

    if len(heap_nums) == 1:
        # 总共只有1路, 返回这第一个值
        return k_way_inputs[0][0]

    h = Heap()
    h.build_min(heap_nums)


    # ------------------- result  ---------------------
    match_set = set()
    match_value = -1

    def push_pop_idx_in_k(node, nums):
        value = node.value
        idx_in_k = node.idx

        nonlocal match_value
        if value == match_value:
            match_set.add(idx_in_k)
            if len(match_set) == k:
                return False
        else:
            match_value = value
            match_set.clear()

            # 剩下的几路不可能有交集了, 因为有些路已经结束了
            if len(nums) != k:
                return False

            match_set.add(idx_in_k)

        cur_input = k_way_inputs[idx_in_k]
        ks_idxs[idx_in_k] += 1
        cur_idx = ks_idxs[idx_in_k]

        if cur_idx >= len(cur_input):
            # 其中1路结束了. 注意不是发现弹出后导致1路结束了, 就立马返回-1.
            # 比如[ [2], [2], [2], [2] ], 每次访问完一个就结束一路, 但是并不结束程序
            # 程序结束的判断, 放到每次弹出后比较match_value长度和match_set长度时判断
            nums[0] = nums[-1]
            nums.pop()
        else:
            nums[0] = Node(cur_input[cur_idx], idx_in_k)

        h.adjust_min(nums, 0)
        return True



    top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)
    while top is not None and will_continue:
        top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)

    if len(match_set) == k:
        return match_value


def k_way_all_intersection(k_way_inputs):
    if len(k_way_inputs) == 0:
        return []

    k = len(k_way_inputs)
    heap_nums = []
    ks_idxs = [0] * k

    for idx, input in enumerate(k_way_inputs):
        if len(input) != 0:
            heap_nums.append(Node(input[0], idx))
        else:
            # 有空, 那么k路没有交集
            return []

    if len(heap_nums) == 1:
        # 总共只有1路, 返回这第一个值
        return k_way_inputs[0]

    h = Heap()
    h.build_min(heap_nums)


    # ------------------- result  ---------------------
    match_set = set()
    match_value = -1
    result = []

    def push_pop_idx_in_k(node, nums):
        value = node.value
        idx_in_k = node.idx

        nonlocal match_value
        nonlocal result
        if value == match_value:
            match_set.add(idx_in_k)
            # print("match", match_value)
            if len(match_set) == k:
                # 这里不用担心去重的问题, 因为同一路的相同数据总是同时在堆顶弹出的
                # 这样重复数据在match 匹配过程中, 因为match_set, 也只能参与一次计数
                # 只有最后一路匹配数据, 第一次匹配到时, 会触发match结果.
                # 但最后一路剩下的重复数据不可能再独立完成match
                result.append(match_value)
        else:
            match_value = value
            match_set.clear()

            # 剩下的几路不可能有交集了, 因为有些路已经结束了
            if len(nums) != k:
                # print("failed", len(nums), k, match_value)
                return False

            match_set.add(idx_in_k)

        cur_input = k_way_inputs[idx_in_k]
        ks_idxs[idx_in_k] += 1
        cur_idx = ks_idxs[idx_in_k]

        if cur_idx >= len(cur_input):
            # 其中1路结束了. 注意不是发现弹出后导致1路结束了, 就立马返回-1.
            # 比如[ [2], [2], [2], [2] ], 每次访问完一个就结束一路, 但是并不结束程序
            # 程序结束的判断, 放到每次弹出后比较match_value长度和match_set长度时判断
            nums[0] = nums[-1]
            nums.pop()
        else:
            nums[0] = Node(cur_input[cur_idx], idx_in_k)

        h.adjust_min(nums, 0)
        return True



    top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)
    while top is not None and will_continue:
        top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)

    # if len(match_set) == k:
    #     return match_value
    return result


def merging_sort_k(k_way_inputs):
    if len(k_way_inputs) == 0:
        return []

    k = len(k_way_inputs)
    heap_nums = []
    ks_idxs = [0] * k

    for idx, input in enumerate(k_way_inputs):
        if len(input) != 0:
            # heap_nums.append(input[0])
            heap_nums.append(Node(input[0], idx))

    if len(heap_nums) == 1:
        # 只有1路
        return k_way_inputs[ heap_nums[0].idx ]

    h = Heap()
    h.build_min(heap_nums)


    # ------------------- result  ---------------------
    result = []

    def push_pop_idx_in_k(node, nums):
        result.append(node.value)
        idx_in_k = node.idx

        ks_idxs[idx_in_k] += 1
        cur_idx = ks_idxs[idx_in_k]

        cur_input = k_way_inputs[idx_in_k]

        if cur_idx >= len(cur_input):
            # 其中1路结束了
            nums[0] = nums[-1]
            nums.pop()

            if len(nums) == 0:
                # 只剩0路了(所有数据都处理完毕了)
                return False

        else:
            nums[0] = Node(cur_input[cur_idx], idx_in_k)

        h.adjust_min(nums, 0)
        return True



    top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)
    while top is not None and will_continue:
        top, will_continue = pop_heap(heap_nums, push_pop_idx_in_k)

    assert top is not None

    # only1_node = heap_nums[0]
    # k_idx = only1_node.idx
    # cur_input = k_way_inputs[k_idx]
    # cur_idx = ks_idxs[k_idx]
    # result.extend( cur_input[cur_idx:] )

    return result


# ------------------- test  ---------------------

def test_k_way_all_intersection():
    inputs = [
        [0, 1, 7, 10],
        [-1, 1, 7, 9],
        [1, 5, 7, 9],
        [1, 2, 3, 7],
        [1, 4, 6, 7],
        [1, 3, 5, 7],
    ]

    results = k_way_all_intersection(inputs)
    print(results)


def test_merging_sort_k():
    inputs = [
        [7, 8, 9, 10],
        [5, 6, 7, 9],
        [3, 5, 7, 9],
        [1, 2, 3, 5],
        [2, 4, 6, 8],
        [2, 3, 5, 7],
        # [1, 2],
        # [3, 4],
    ]

    result = merging_sort_k(inputs)
    print("[merging sort result]", result)

    # print(len(result))


def test_min_inter():
    inputs = [
        [0, 1, 7, 10],
        [-1, 3, 7, 9],
        [1, 5, 7, 9],
        [1, 2, 3, 7],
        [1, 4, 6, 7],
        [1, 3, 5, 7],
    ]

    result = k_way_min_intersection(inputs)
    print("[min inter]", result)


def main():
    print("start main")
    test_merging_sort_k()
    test_min_inter()
    test_k_way_all_intersection()

if __name__ == "__main__":
    main()
